package primary.code04_List;

import primary.util.ListUtils;

/**
 * 复制含有随机节点指针的链表
 * 将复制节点插入原链表中，以获取相对位置，然后再分离新链表
 * <p>
 * 思路：
 * 1. 插入节点
 * 2. 设置随机节点
 * 3. 分裂节点
 */
public class Code05_CopyRandomList {

    private static RandomNode c1;

    private static RandomNode copyList(RandomNode head) {
        if (head == null || head.next == null) return head;
        //复制节点，并插入到原节点后方
        RandomNode cur = head;
        while (cur != null) {
            RandomNode copyNode = new RandomNode(cur.getData());
            RandomNode temp = cur.next;
            cur.next = copyNode;
            copyNode.next = temp;
            cur = cur.next.next;
        }
        //设置随机节点
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;//注意
            cur = cur.next.next;
        }
        //分离
        RandomNode copyList = head.next;
        cur = head;
        while (cur != null) {
            RandomNode temp = cur.next;
            cur.next = cur.next.next;
            temp.next = temp.next == null ? null : temp.next.next;//注意
            cur = cur.next;
        }
        return copyList;
    }

    private static RandomNode copyListTest(RandomNode head) {
        // insert
        RandomNode cur = head;
        while (cur != null) {
            RandomNode copy = new RandomNode(cur.data);
            copy.next = cur.next;
            cur.next = copy;
            cur = cur.next.next;
        }

        // copy random
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next; // 注意null
            cur = cur.next.next;
        }


        // split
        cur = head;
        RandomNode result = cur.next;
        while (cur != null) {
            RandomNode copy = cur.next;
            cur.next = copy.next;
            copy.next = cur.next == null ? null : cur.next.next; // 注意null
            cur = cur.next;
        }
        return result;
    }


    /**
     * 原链表：111-->23(41)-->18-->41-->25(18)-->18-->
     * 复制链表：111-->23(41)-->18-->41-->25(18)-->18-->
     * 复制链表：111-->23(41)-->18-->41-->25(18)-->18-->
     */
    public static void main(String[] args) {
        RandomNode RandomNode1 = new RandomNode(111);
        RandomNode RandomNode2 = new RandomNode(23);
        RandomNode RandomNode3 = new RandomNode(18);
        RandomNode RandomNode4 = new RandomNode(41);
        RandomNode RandomNode5 = new RandomNode(25);
        RandomNode RandomNode6 = new RandomNode(18);
        RandomNode1.next = RandomNode2;
        RandomNode2.next = RandomNode3;
        RandomNode2.random = RandomNode4;
        RandomNode3.next = RandomNode4;
        RandomNode4.next = RandomNode5;
        RandomNode5.next = RandomNode6;
        RandomNode5.random = RandomNode3;
        System.out.println("原链表：" + ListUtils.printList(RandomNode1));
        System.out.println("复制链表：" + ListUtils.printList(copyList(RandomNode1)));
        System.out.println("复制链表：" + ListUtils.printList(copyListTest(RandomNode1)));
    }
}
